home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 11 / Cream of the Crop 11-1.iso / games / ted5.zip / IGRABSRC.ZIP / JHUFF.C < prev    next >
C/C++ Source or Header  |  1993-02-04  |  8KB  |  431 lines
  1. /**************************************************************
  2.     JHUFF.C -- A rle/huffman Data Compression Program
  3. **************************************************************/
  4.  
  5. #include "igrab.h"
  6. #pragma hdrstop
  7.  
  8. unsigned char huge *infile,
  9.           huge *outfile;
  10.  
  11. long inlength,outlength;
  12.  
  13. long counts[256];
  14.  
  15. unsigned huffbits[256];
  16. unsigned long huffstring[256];
  17.  
  18. huffnode nodearray[256];    // 256 nodes is worst case
  19.  
  20. /*
  21. =============================================================================
  22.  
  23.                COMPRESSION SUBS
  24.  
  25. =============================================================================
  26. */
  27.  
  28.  
  29.  
  30. /*
  31. ======================
  32. =
  33. = CountBytes
  34. =
  35. = Adds the bytes in the pointed to area to the counts array
  36. = If this is the first segment, make sure counts is zerod
  37. =
  38. ======================
  39. */
  40.  
  41. void CountBytes (unsigned char huge *start, long length)
  42. {
  43.   long i;
  44.  
  45.   while (length--)
  46.     counts[*start++]++;
  47. }
  48.  
  49. /*
  50. =======================
  51. =
  52. = FindLeast
  53. =
  54. = Returns the byte with the lowest counts value
  55. =
  56. =======================
  57. */
  58.  
  59. int FindLeast (void)
  60. {
  61.   int i,least;
  62.   long low = 0x7fffffff;
  63.  
  64.   for (i=0;i<256;i++)
  65.     if (counts[i]<low)
  66.     {
  67.       low = counts[i];
  68.       least = i;
  69.     }
  70.  
  71.   return least;
  72. }
  73.  
  74. /*========================================================================*/
  75.  
  76. /*
  77. ==================
  78. =
  79. = TraceNode
  80. =
  81. = A recursive function that follows all leaves of nodearray and fills in
  82. = coding tables huffbits and huffstring.
  83. =
  84. ==================
  85. */
  86.  
  87. void TraceNode (int nodenum,int numbits,unsigned long bitstring)
  88. {
  89.   unsigned bit0,bit1;
  90.  
  91.   bit0 = nodearray[nodenum].bit0;
  92.   bit1 = nodearray[nodenum].bit1;
  93.  
  94.   numbits++;
  95.  
  96.  
  97.   if (bit0 <256)
  98.   {
  99.     huffbits[bit0]=numbits;
  100.     huffstring[bit0]=bitstring;        // just added a zero in front
  101.   }
  102.   else
  103.   {
  104.     if (numbits<24)            // if the string is this long, its 0
  105.       TraceNode (bit0-256,numbits,bitstring);
  106.   }
  107.  
  108.   if (bit1 <256)
  109.   {
  110.     huffbits[bit1]=numbits;
  111.     huffstring[bit1]=bitstring+ (1ul<<(numbits-1));    // add a one in front
  112.     if (huffbits[bit1]>24 && counts[bit1])
  113.     {
  114.       puts("Error: Huffman bit string went over 32 bits!");
  115.       exit(1);
  116.     }
  117.   }
  118.   else
  119.   {
  120.     if (numbits<24)            // if the string is this long, its 0
  121.      TraceNode (bit1-256,numbits,bitstring+(1ul<<(numbits-1)));
  122.   }
  123. }
  124.  
  125.  
  126. /*
  127. =======================
  128. =
  129. = Huffmanize
  130. =
  131. = Takes the counts array and builds a huffman tree at
  132. = nodearray, then builds a codeing table.
  133. = 
  134. =======================
  135. */
  136.  
  137. void Huffmanize (void)
  138. {
  139. //
  140. // codes are either bytes if <256 or nodearray numbers+256 if >=256
  141. //
  142.   unsigned value[256],code0,code1;
  143. //
  144. // probablilities are the number of times the code is hit or $ffffffff if
  145. // it is allready part of a higher node
  146. //
  147.   unsigned long prob[256],low,workprob;
  148.  
  149.   int i,worknode,bitlength;
  150.   unsigned long bitstring;
  151.  
  152.   memset(huffstring,0,sizeof(huffstring));
  153.   memset(huffbits,0,sizeof(huffbits));
  154.  
  155. //
  156. // all possible leaves start out as bytes
  157. //
  158.   for (i=0;i<256;i++)
  159.   {
  160.     value[i]=i;
  161.     prob[i]=counts[i];
  162.   }
  163.  
  164. //
  165. // start selecting the lowest probable leaves for the ends of the tree
  166. //
  167.  
  168.   worknode = 0;
  169.   while (1)    // break out of when all codes have been used
  170.   {
  171.     //
  172.     // find the two lowest probability codes
  173.     //
  174.  
  175.     code0=0xffff;
  176.     low = 0x7ffffffff;
  177.     for (i=0;i<256;i++)
  178.       if (prob[i]<low)
  179.       {
  180.     code0 = i;
  181.     low = prob[i];
  182.       }
  183.  
  184.     code1=0xffff;
  185.     low = 0x7fffffff;
  186.     for (i=0;i<256;i++)
  187.       if (prob[i]<low && i != code0)
  188.       {
  189.     code1 = i;
  190.     low = prob[i];
  191.       }
  192.  
  193.     if (code1 == 0xffff)
  194.     {
  195.       if (value[code0]<256)
  196.     errout("Weirdo huffman error: last code wasn't a node!");
  197.       if (value[code0]-256 != 254)
  198.     errout("Weirdo huffman error: headnode wasn't 254!");
  199.       break;
  200.     }
  201.  
  202.     //
  203.     // make code0 into a pointer to work
  204.     // remove code1 (make 0xffffffff prob)
  205.     //
  206.     nodearray[worknode].bit0 = value[code0];
  207.     nodearray[worknode].bit1 = value[code1];
  208.  
  209.     value[code0] = 256 + worknode;
  210.     prob[code0] += prob[code1];
  211.     prob[code1] = 0xffffffff;
  212.     worknode++;
  213.   }
  214.  
  215. //
  216. // done with tree, now build table recursively
  217. //
  218.  
  219.   TraceNode (254,0,0);
  220.  
  221. }
  222.  
  223. /*========================================================================*/
  224.  
  225. /*
  226. ===============
  227. =
  228. = OptimizeNodes
  229. =
  230. = Goes through a huffman table and changes the 256-511 node numbers to the
  231. = actular address of the node.  Must be called before HuffExpand
  232. =
  233. ===============
  234. */
  235.  
  236. void OptimizeNodes (huffnode *table)
  237. {
  238.   huffnode *node;
  239.   int i;
  240.  
  241.   node = table;
  242.  
  243.   for (i=0;i<255;i++)
  244.   {
  245.     if (node->bit0 >= 256)
  246.       node->bit0 = (unsigned)(table+(node->bit0-256));
  247.     if (node->bit1 >= 256)
  248.       node->bit1 = (unsigned)(table+(node->bit1-256));
  249.     node++;
  250.   }
  251. }
  252.  
  253. /*========================================================================*/
  254.  
  255. /*
  256. ======================
  257. =
  258. = HuffCompress
  259. =
  260. = The file must be counted with CountBytes and then Huffmanized first
  261. =
  262. ======================
  263. */
  264.  
  265. long HuffCompress (unsigned char huge *source, long length,
  266.   unsigned char huge *dest)
  267. {
  268.   long outlength;
  269.   unsigned long string;
  270.   unsigned biton,bits;
  271.   unsigned char byte;
  272.  
  273.  
  274.   if (length<60000)
  275.   {
  276.     FastHuffCompress(source,length,dest);
  277.     return;
  278.   }
  279.  
  280.   outlength = biton = 0;
  281.  
  282.   *(long huge *)dest=0;        // so bits can be or'd on
  283.  
  284.   while (length--)
  285.   {
  286.     byte = *source++;
  287.     bits = huffbits[byte];
  288.     string = huffstring[byte] << biton;
  289.     *(long huge *)(dest+1)=0;    // so bits can be or'd on
  290.     *(long huge *)dest |= string;
  291.     biton += bits;        // advance this many bits
  292.     dest+= biton/8;
  293.     biton&=7;            // stay under 8 shifts
  294.     outlength+=bits;
  295.   }
  296.  
  297.   return (outlength+7)/8;
  298. }
  299.  
  300. /*========================================================================*/
  301.  
  302. /*
  303. ======================
  304. =
  305. = HuffExpand
  306. =
  307. ======================
  308. */
  309.  
  310. void HuffExpand (unsigned char huge *source, unsigned char huge *dest,
  311.   long length,huffnode *hufftable)
  312. {
  313.   unsigned bit,byte,node,code;
  314.   unsigned sourceseg,sourceoff,destseg,destoff,endseg,endoff;
  315.   huffnode *nodeon,*headptr;
  316.  
  317.   nodeon = headptr = hufftable+254;    // head node is allways node 254
  318.  
  319.   bit = 1;
  320.   byte = *source++;
  321.  
  322.   while (length)
  323.   {
  324.     if (byte&bit)
  325.       code = nodeon->bit1;
  326.     else
  327.       code = nodeon->bit0;
  328.  
  329.     bit<<=1;
  330.     if (bit==256)
  331.     {
  332.       bit=1;
  333.       byte = *source++;
  334.     }
  335.  
  336.     if (code<256)
  337.     {
  338.       *dest++=code;
  339.       nodeon=headptr;
  340.       length--;
  341.     }
  342.     else
  343.       nodeon = (huffnode *)code;
  344.   }
  345.  
  346.  
  347. #if 0
  348.  
  349.   source++;    // normalize
  350.   source--;
  351.   dest++;
  352.   dest--;
  353.  
  354.   sourceseg = FP_SEG(source);
  355.   sourceoff = FP_OFF(source);
  356.   destseg = FP_SEG(dest);
  357.   destoff = FP_OFF(dest);
  358.  
  359.   length--;
  360. //
  361. // al = source byte
  362. // cl = bit in source (1,2,4,8,...)
  363. // dx = code
  364. //
  365. // ds:si source
  366. // es:di dest
  367. // ss:bx node pointer
  368. //
  369.  
  370. asm     mov    bx,headptr
  371. asm    mov    cl,1
  372.  
  373. asm    mov    si,sourceoff
  374. asm    mov    di,destoff
  375. asm    mov    es,destseg
  376. asm    mov    ds,sourceseg
  377.  
  378. asm    lodsb            // load first byte
  379.  
  380. expand:
  381. asm    test    al,cl        // bit set?
  382. asm    jnz    bit1
  383. asm    mov    dx,ss:bx    // take bit0 path from node
  384. asm    jmp    gotcode
  385. bit1:
  386. asm    mov    dx,ss:bx+2    // take bit1 path
  387.  
  388. gotcode:
  389. asm    shl    cl,1        // advance to next bit position
  390. asm    jnc    sourceup
  391. asm    lodsb
  392. asm    cmp    si,0x10        // normalize ds:si
  393. asm      jb    sinorm
  394. asm    mov    cx,ds
  395. asm    inc    cx
  396. asm    mov    ds,cx
  397. asm    xor    si,si
  398. sinorm:
  399. asm    mov    cl,1        // back to first bit
  400.  
  401. sourceup:
  402. asm    or    dh,dh        // if dx<256 its a byte, else move node
  403. asm    jz    storebyte
  404. asm    mov    bx,dx        // next node = (huffnode *)code
  405. asm    jmp    expand
  406.  
  407. storebyte:
  408. asm    mov    [es:di],dl
  409. asm    inc    di        // write a decopmpressed byte out
  410. asm    mov    bx,headptr    // back to the head node for next bit
  411.  
  412. asm    cmp    di,0x10        // normalize es:di
  413. asm      jb    dinorm
  414. asm    mov    dx,es
  415. asm    inc    dx
  416. asm    mov    es,dx
  417. asm    xor    di,di
  418. dinorm:
  419.  
  420. asm    sub    WORD PTR ss:length,1
  421. asm    jnc    expand
  422. asm      dec    WORD PTR ss:length+2
  423. asm    jns    expand        // when length = ffff ffff, done
  424.  
  425. asm    mov    ax,ss
  426. asm    mov    ds,ax
  427.  
  428. #endif
  429.  
  430. }
  431.